#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define maxsize 10
#define INF 65535
typedef struct agraph
{
	int edges[maxsize][maxsize];
	char vex[maxsize];
	int n;
}*graph;
void Floyd(graph g,int path[][maxsize],int dist[][maxsize])
{
	int i,j,k;
	for(i=0;i<g->n;i++) //初始化
		for(j=0;j<g->n;j++)
		{
			dist[i][j]=g->edges[i][j];
			path[i][j]=-1;
		}
	for(k=0;k<g->n;k++)  //选择一个顶点k进行更新
		for(i=0;i<g->n;i++)
			for(j=0;j<g->n;j++)
				if(dist[i][j]>dist[i][k]+dist[k][j])
				{
					dist[i][j]=dist[i][k]+dist[k][j];
					path[i][j]=k;
				}
}
int fun(graph g)
{
	int dist[maxsize][maxsize],path[maxsize][maxsize];
	Floyd(g,path,dist);
	int i,j,max=0;
	for(i=0;i<g->n;i++)
		for(j=0;j<g->n;j++)
			if(dist[i][j]>max)
				max=dist[i][j];
	return max;
}

int main(){
    graph g=(graph)malloc(sizeof(struct agraph));
	char arr[maxsize]={'a','b','c','d','e','f','g'};
	int arri[][maxsize]={
		{0,12,INF,INF,INF,16,14},
		{12,0,10,INF,INF,7,INF},
		{INF,10,0,3,5,6,INF},
		{INF,INF,3,0,4,INF,INF},
		{INF,INF,5,4,0,2,8},
		{16,7,6,INF,2,0,9},
		{14,INF,INF,INF,8,9,0}
	};
	g->n=7;
	// 数组定义与初始化分开时，只能进行单个元素赋值，而不能进行统一赋值
	for(int i=0;i<g->n;i++){
		g->vex[i]=arr[i];
	}
	for(int i=0;i<g->n;i++){
		for(int j=0;j<g->n;j++){
			g->edges[i][j]=arri[i][j];
		}
	}
	printf("%d",fun(g));
    return 0;
}